This invention relates to data storage for computers, and more particularly to use of physical change data for backup and restoring of data.
Virtually all computer applications (or programs) rely on storage. This storage can be used for both storing the computer code and for storing data manipulated by the code. (The term xe2x80x9cdataxe2x80x9d refers to any information, including formatting information, executable code and data for manipulation by an application program.)
Storage technology has developed in a variety of different directions. Accordingly, a wide variety of storage systems are available. It has become impractical, therefore, for the person writing the computer application to also be responsible for detailed control over how data is stored on the storage system.
For this (and other) reasons, application programs typically run on an operating system (e.g., Unix, Windows, MS DOS, Linux, and the many variations of each). Once again, however, the operating system may be used with a variety of storage systems.
It would be highly inefficient to have to change the operating system, or the application programs, every time a change is made to physical storage. As a result, various layers of abstraction have evolved for viewing how data is actually stored in the storage system.
FIG. 1 illustrates one way of viewing the layers of abstraction. At the top level 10, the application program may assume that data is stored in a manner that has very little to do with how the data is placed onto the physical device. For example, the application may view the storage system as containing a number of directories and data files within the directories. Thus, in an application written for use in the Unix operating system, the application will assume that files are stored according to the Unix directory structure (including hierarchical directories and files located within the directories). This assumed organization of physical storage may have very little to do with how that data is actually stored onto the actual storage devices. This view may be referred to as the xe2x80x9clogical viewxe2x80x9d because of the separation between the logical view of data from the application level is divorced from any view of how the data is physically stored.
The application level 10 then interfaces with the file system level 12. The file system level is concerned with how files are stored on disks and how to make everything work efficiently and reliably. Thus, the file system level may be responsible for storing directory structure, and for breaking up files into constituent data blocks for storage onto a physical storage system. For example, in most implementations of Unix, each file has an associated I-node. This node may contain accounting and protection information and, additionally, a set of pointers to data blocks.
Relatively early in the development of computer systems, disk drives became a fundamental device for storage. Accordingly, computer operating systems have been developed assuming that memory will rely on input/output (xe2x80x9cI/Oxe2x80x9d) to a disk drive. The file system 12, therefore, may assume one or more xe2x80x9cvolumesxe2x80x9d which correspond to a physical storage unit such as a disk drive (or any other unit of storage), with data stored in blocks on the disk drive.
The demand for storage to be available for use by applications has sky rocketed. As a result, a number of separate physical devices may be required to accommodate the total amount of storage required for a system. In addition, storage systems are often changed or reconfigured.
To insulate the operating system from any changes within the physical device storage system, some mechanism is often employed to flexibly map a standard (volume) view of physical storage onto an actual physical storage system. The logical volume manager 14 of FIG. 1 can help achieve this function by mapping the file system view of data storage into an intermediate layer.
Finally, the actual storage reading and writing (and, potentially, additional mapping onto physical storage devices) occurs within the physical storage system level 16, as illustrated in FIG. 1. Thus, for example, the logical volume manager may map the file system level view of data into volume sizes corresponding to fixed physical storage segment sizes for storage on a physical device (e.g, block sizes). The physical storage system level may then map the logical volume manager level volumes onto physical storage segments (e.g., hyper-volumes discussed below).
Logical volume managers have been implemented for use with the HP-UX by HP and by VERITAS operating systems, as examples. The Symmetrix line of storage systems, available from EMC Corporation, of Hopkinton, Mass., is one system capable of mapping hyper-volumes onto physical devices. (The Symmetrix product line of integrated cached disk arrays is described in numerous publications form EMC Corporation, including the Symmetrix model 55xx product manual, p-n200-810-550, rev.f, February, 1996.)
In the above examples, the mapping of application level data into actual physical storage occurs across four levels: application level to file system level; file system level to LVM level; LVM level to physical storage system level; and physical storage system level to the actual physical storage devices. More or fewer levels of mapping can be done. In some systems, for example, only one level of mapping is performed, e.g., mapping from the application level directly onto actual physical storage devices. In many systems, the mapping stage at the LVM level is omitted. Similarly, in many systems, no mapping is done at the physical storage level (e.g., data is stored directly onto actual devices corresponding to the format of the preceding level and without any further mapping onto physical storage components.)
FIG. 2A illustrates an example of the mapping that may be performed by the logical volume manager 14 and the physical storage system 16, to store data onto actual physical devices. The application/file system""s view of the storage system contemplates three separate storage devicesxe2x80x94volume A 20, volume B 21, and volume C 22. Thus, as far as the file system level 12 can discern, the system consists of three separate storage devices 20-22. Each separate storage device may be referred to as a xe2x80x9cvirtual volume,xe2x80x9d or xe2x80x9cvirtual disk.xe2x80x9d This reflects that the operating system""s view of the storage device structure may not correspond to the actual physical storage system implementing the structure (hence, xe2x80x9cvirtualxe2x80x9d). Unlike the application level 10, however, the file system 12 perspective is as if the file system 12 were dealing with raw physical devices or volumes.
As far as the file system level is concerned, the virtual volumes may be divided up into xe2x80x9cpartitions,xe2x80x9d which are continuous segments of storage. These partitions are, in fact, xe2x80x9cvirtualxe2x80x9d partitions, because the partition may actually be stored across a variety of physical storage segments (e.g., hyper-volumes).
In FIG. 2A, the data is physically stored on the physical storage devices 24-26. In this particular example, although there are three physical devices 24-26 and three volumes 20-22, there is not a one to one mapping of the virtual volumes to physical devices. In this particular example, the data in volume A 20 is actually stored on physical devices 24-26, as indicated at 20a, 20b and 20c. In this example, volume B is stored entirely on physical device 24, as indicated at 22a, 22b. Finally, volume C is stored on physical device 24 and physical device 26 as indicated at 21a, 21b. 
In this particular example, the boxes 20a-20c, 21a-21b and 22a-22b represent contiguous segments of storage within the respective physical devices 24-26. These contiguous segments of storage may, but need not, be of the same size. The segments of storage may be referred to as xe2x80x9chyper-volumes,xe2x80x9d and correspond to segments of physical storage that can be used as components when constructing a virtual volume for use by the file system. A hypervolume may be comprised of a number of xe2x80x9cdata blocks.xe2x80x9d A data block is a unit of storage (e.g., a 512 byte block) that is written or read at one time from the physical storage device.
Array management software running on a general purpose processor (or some other mechanism such as a custom hardware circuit) 23 translates requests from a host computer (not shown) (made assuming the logical volume structure 20-22) into requests that correspond to the way in which the data is actually stored on the physical devices 24-26. In practice, the array management software 23 may be implemented as a part of a unitary storage system that includes the physical devices 24-26, may be implemented on a host computer, or may be done in some other manner.
In FIG. 2A the array management software 23 performs the functions of both the logical volume manager 14 (if present) and the physical storage level 16, by mapping the file system""s virtual volumes 20-22 into segments that can be stored onto physical devices 24-26. The array management software 23 also performs the functions of the physical storage system level 16, by determining where to store the hyper-volumes 20A-20C, 21A-21B and 22A-22B.
The physical storage devices shown in the example of FIG. 2A are disk drives. A disk drive may include one or more disks of a recording media (such as a magnetic recording medium or an optical recording medium). Information can be written and read from this storage medium for storage purposes. The recording medium is typically in the form of a disk that rotates. The disk generally includes a number of tracks on which the information is recorded and from which the information is read. In a disk drive that includes multiple disks, the disks are conventionally stacked so that corresponding tracks of each disk overlie each other. In this case, specification of a single track on which information is stored within the disk drive includes not only specification of an individual track on a disk, but also which of the multiple disks the information is stored on. The physical storage devices for use with the present invention may, however, be any other storage mechanism.
FIG. 2B illustrates one example of mapping between the top level of abstractionxe2x80x94the application levelxe2x80x94to the actual physical storage level. An application level file 200 includes visual information. This information is in the form of a conventional file and includes a series of bits.
When the application level file is mapped onto physical storage, the application level file may be converted into segments of the individual bits, e.g., segment 203. Thus, a segment of the application level file 203 is mapped (for example according to the general mapping structure described above with reference to FIG. 1) onto actual physical storage devices 204-206. In this example, the first segment of bits in 203 in the application level file 200 is mapped onto physical storage device 204, at a portion 208 of the physical storage device 204. As shown in FIG. 2B, the individual segments of bits in the application level file 200 may be mapped anywhere among a plurality of actual physical storage devices. The granularity of the segments of bits (e.g., segment 203) may correspond to one of a variety of different levels. For example, the granularity of the segments may be a 512 byte data block. In another embodiment, the granularity may correspond to the amount of data stored in a track of the physical storage device 204-206 (when the physical storage devices are disk drives).
In a system including an array of physical disk devices, such as disk devices 24-26 of FIG. 2A, each device typically performs error detection and/or correction for the data stored on the particular physical device. Accordingly, each individual physical disk device detects when it does not have valid data to provide and, where possible, corrects the errors. Even where error correction is permitted for data stored on the physical device, however, a catastrophic failure of the device would result in the irrecoverable loss of data.
Accordingly, storage systems have been designed which include redundant storage capacity. A variety of ways of storing data onto the disks in a manner that would permit recovery have developed. A number of such methods are generally described in the RAIDbook, A Source Book For Disk Array Technology, published by the RAID Advisory Board, St. Peter, Minn. (5th Ed., February, 1996). These systems include xe2x80x9cRAIDxe2x80x9d storage systems. RAID stands for Redundant Array of Independent Disks.
FIG. 3A illustrates one technique for storing redundant information in a RAID system. Under this technique, a plurality of physical devices 31-33 include identical copies of the data. Thus, the data M1 can be xe2x80x9cmirroredxe2x80x9d onto a portion 31a of physical device 31, a portion 32a of physical device 32 and a portion 33a of physical device 33. In this case, the aggregate portions of the physical disks that store the duplicated data 31a, 32a and 33a may be referred to as a xe2x80x9cmirror group.xe2x80x9d The number of places in which the data M1 is mirrored is generally selected depending on the desired level of security against irrecoverable loss of data.
In a mirror group, the copies are xe2x80x9clinked.xe2x80x9d That is, any update to one mirror causes an update to each other mirror in the group.
FIG. 3A shows three physical devices 31-33 which appear to be located in close proximity, for example within a single storage system unit. For very sensitive data, however, one or more of the physical devices that hold the mirrored data may be located at a remote facility.
xe2x80x9cRAID 1xe2x80x9d is an example of data redundancy through mirroring of data. In a RAID 1 architecture, a number of different mechanisms may be used for determining how to access and update data to improve, for example, performance of the storage system. In any event, a RAID 1 architecture certainly has the ability to recover lost data. Unfortunately, the RAID 1 architecture multiplies the cost of physical storage by the number of xe2x80x9cmirrorsxe2x80x9d included in the mirror group.
FIG. 3B illustrates a solution that requires less added storage. In FIG. 3B, data is stored at locations 34a-34d. In this particular example, the physical device 33 includes parity information P1 at 35a, 35b. The parity information is generated by a simple exclusive-OR (xe2x80x9cXORxe2x80x9d) of the corresponding bits of data. Thus, the parity information P1 would be generated by XORing the corresponding bits of the data D1 and data D2.
A variety of mechanisms are known for distributing the parity information on the physical devices. In the example shown in FIG. 3B, all of the parity information is stored on a single physical device 33. In other cases, the parity information may be distributed across the physical devices.
FIG. 4 illustrates the concept that, within a given disk array, there is no need for all of the data to follow the same redundancy rule. In FIG. 4, a first group of storage segments on physical devices 40-42 form a mirror group 44. In the mirror group 44, the entire contents of a single logical volume (HV-A) are mirrored on three different physical devices 40-42.
In FIG. 4, a single virtual volume is stored on the fourth physical device 43, without any redundancy information, as indicated at 46.
Finally, a last group of data segments 45, on all four physical devices 40-43, implement a parity redundancy scheme. In this particular example, the parity information is stored in segments of memory on two different physical devices 42-43, as indicated at 47a and 47b. 
The storage system of FIG. 4 contains redundant information that permits recovery from errors, including use of a mirror for data located at a remote facility, that also permits recoveries from catastrophic failure.
According to one embodiment of the present invention, a method of backing up data in a computer storage system is disclosed. According to this embodiment, segments of data in the memory that have changed are identified. A backup is formed of the identified changed segments, omitting at least one of the segments that has not been changed. In one embodiment, the segments are formed in units corresponding to physical segments of storage in the computer system, such as a block of data or a track in a disk drive. This embodiment may further comprise identifying segments that have changed since a preceding backup and at a second time, forming a second backup that includes the changed segments from the time of the preceding backup to the second time. In another embodiment, the second backup is formed of segments that have been changed since the first backup. The segments may constitute a logical element, and mapping between locations of the segments in the logical element to the locations in physical storage may be performed.
According to another embodiment of the present invention, a backup storage system is disclosed. According to this embodiment, a differential backup generator receives information specifying which physical segments of storage in a physical storage device have changed, and generates a differential backup of the changed segments accordingly. This embodiment also includes a backup storage device to store the differential backup. The backup storage system according to this embodiment may include means for tracking which of the physical segments have been changed since a preceding level zero backup. In another embodiment, the physical storage device may include means for tracking which of the physical segments have been changed since a preceding differential backup.
According to another embodiment of the present invention, a method of forming a complete backup copy of a plurality of segments of data in a computer storage system is disclosed. According to this embodiment, an earlier backup of the plurality of segments is provided. In addition, a later copy of at least one of the segments, corresponding to a time after the earlier backup, is provided. A complete backup is then formed from the earlier backup copy and the first later copy. According to another embodiment, additional later copies (such as differential backups) may be used to generate the complete copy.
According to another embodiment of the present invention, a backup storage system is disclosed. This embodiment includes means for storing an earlier backup copy of a plurality of segments corresponding to an earlier time and for storing a first later copy of at least one of the segments corresponding to a time after the earlier time. This embodiment further includes means for performing a complete backup from the earlier backup copy and the first later copy.
According to another embodiment of the present invention, a backup system for storing backup information in a computer storage system is disclosed. According to this embodiment, a first memory unit storing a backup copy of a plurality of physical segments is provided. This backup copy corresponds to a first time. In addition, the backup system includes a second memory unit storing a later copy of at least one of the physical segments, corresponding to a time after the first time.
According to another embodiment of the present invention, a method of restoring a primary copy of a plurality of segments of data stored on a physical storage device is disclosed. According to this embodiment, the plurality of segments forms a logical element and the restoration is to a state of the primary copy of a target time. This embodiment includes steps of identifying which of the segments of data have changed since the target time and restoring the identified changed segments to the primary copy, while retaining at least one of the segments already in the primary copy. The effect of the method is to undo changes that have been performed.
According to another embodiment of the present invention, a backup storage system is disclosed. According to this embodiment, a restore controller is included to restore a primary copy of a plurality of segments of the data stored on the physical storage device, the plurality of segments forming a logical element, to a state at a target time. This embodiment further includes a backup memory system to store and retrieve copies of the segments corresponding to a time at least as early as the target time. Finally, in this embodiment, the restore controller comprises a mapper to receive information identifying which of the physical segments in the primary copy have been changed since the target time and to identify corresponding copies of the changed segments in the backup memory system.
According to another embodiment of the present invention, a backup storage system is disclosed. According to this embodiment, the system restores a primary copy of a plurality of data stored on a physical storage device, the plurality of segments forming a logical element, again to a state corresponding to a target time. According to this embodiment, the system includes means for identifying which of the segments of data have changed since the target time and means for restoring the identified changed segments.
According to another embodiment of the present invention, a method of backing up a primary copy of a plurality of data segments at a backup time is disclosed. According to this embodiment, a backup copy of the primary copy is provided. The segments of data of the primary copy that have been changed since an earlier time are identified. A differential backup is formed, backing up the corresponding copies of the segments of the backup copy for those segments to be changed. After the differential backup has been formed, the backup copy is updated from the primary copy. The backup copy may be a full level zero backup and may also be a mirror of the primary copy.
According to another embodiment of the present invention, a method of backing up a copy of a plurality of data segments at a backup time is disclosed. According to this embodiment, the data segments to be changed are identified. Before changing the identified segments, however, a differential backup of those segments is formed.
According to another embodiment of the present invention, a method of restoring a primary copy of a plurality of data segments to correspond to a target time is disclosed. According to this embodiment, a first differential backup copy of less than all of the data segments of the primary copy is formed. The first differential backup copy corresponds to a first time, more recent than the target time. The first differential backup copy is then used to identify segments of the primary copy that have been changed since the target time. Finally, the identified segments are restored. The step of restoring the identified segments may correspond to using a differential backup copy of the segment from the target time or before the target time.
According to another embodiment of the present invention, a method of restoring a primary copy of a plurality of data segments to their state at a target time is disclosed. According to this embodiment, a backup copy of the primary copy is provided. The backup copy corresponds to a first time, which is more recent than the target time. A first differential backup copy is provided, the first differential backup copy being no more recent than the target time. According to this embodiment, at least one of the segments of the backup copy is replaced with a corresponding segment of the first differential backup. The primary copy may then be restored from the backup copy. The backup copy may be a mirror of the primary copy.
According to another embodiment of the present invention, a backup storage system to backup a primary copy of a plurality of data segments is disclosed. According to this embodiment, the system includes a backup manager to generate differential backups just before the segments are updated. This system further includes a backup memory to store the differential backups.
According to another embodiment of the present invention, a backup system for storing backups for a first and a second time is disclosed. The first time is an earlier time than the second time. According to this embodiment, a first memory unit stores a backup copy of a plurality of physical segments of memory of a computer storage system, the physical segments constituting a logical element, the backup copy corresponding to the second (later) time. This system also includes a second memory unit storing an earlier differential backup copy for the physical segments, which corresponds to the first (earlier) time.